public class java2024_5_5 {
    //    public static void main(String[] args) {
//        //插入排序
//        int[] arr = {1, 4, 2, 3, 6, 5, 9, 7, 8, 10};
//        int length = arr.length;
//        InsertSort(arr, length);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i] + " ");
//        }
//    }
//    //插入排序
//    public static void InsertSort(int[] arr, int sz) {
//        for (int i = 0; i < sz - 1; i++) {
//            int end = i;
//            int key = arr[end + 1];
//            while (end >= 0) {
//                if (arr[end] > key) {
//                    arr[end + 1] = arr[end];
//                    end--;
//                } else {
//                    break;
//                }
//            }
//            arr[end + 1] = key;
//        }
//    }
//    public static void main(String[] args) {
//        int[] arr = {1, 4, 2, 5, 3, 8, 9, 6, 7, 10};
//        int length = arr.length;
//        ShellSort(arr, length);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i] + " ");
//        }
//    }
//
//    //希尔排序
//    public static void ShellSort(int[] arr, int n) {
//        int gap = n;
//        while (gap > 1) {
//            gap /= 2;
//            for (int i = 0; i < n - gap; i++) {
//                int end = i;
//                int key = arr[end + gap];
//                while (end >= 0) {
//                    if (arr[end] > key) {
//                        arr[end + gap] = arr[end];
//                        end -= gap;
//                    } else {
//                        break;
//                    }
//                }
//                arr[end + gap] = key;
//            }
//        }
//    }
    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 7, 3, 5, 6, 10, 9,8};
        int length = arr.length;
        HeapSort(arr, length);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

    //向下调整算法
    public static void AdjuctDown(int[] arr, int n, int root) {
        int parent = root;
        int child = 2 * parent + 1;
        while (child < n) {
            if (arr[child + 1] > arr[child] && child + 1 < n) {
                child++;
            }
            if (arr[parent] < arr[child]) {
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    //建堆
    public static void CreatHeap(int[] arr, int n) {
        for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
            AdjuctDown(arr, n, i);
        }
    }

    //堆排序
    public static void HeapSort(int[] arr, int n) {
        int end = n;
        while (end > 1) {
            CreatHeap(arr, end);
            int temp = arr[0];
            arr[0] = arr[end - 1];
            arr[end - 1] = temp;
            end--;
        }
    }
}
